The fun part about this solution is that if you switch the order of the for loops in the code, your answer almost doubles! Learnt it the hard way.

If you're wondering why, here's a hint:

To make an amount of 3 with two coin denominations 1 and 2, you can go:
1 + 2 = 3
2 + 1 = 3
Both mean the same thing, in this question.

great article...it would be great if you guys can first explain top down approach..then bottom up

Although the implementation looks super easy and so does the explanation neither of them is. Moreover, it is dangerously confusing. The dp relationship dp[x] = dp[x] + dp[x - coin] depends on itself, which is not permitted for dynamic programming. Optimal substructure is not shown. So this is indeed a solution, but it is not a dynamic programming one (strictly speaking at least). The problem can be solved with DP, however, for which you need a two dimensional DP array.

I would say the dp formula dp[x] += dp[x - coin] can be explained as
The combination of i number of coins to make change for j amount = The combination when we not using ith coin to make change for j amount + The combination when we use ith coin to make change for j amount.

It likes knapsack problem, calculate the result when we pick the current coin and not pick it and get the total

This explanation explains how to do the problem, but doesn't fully explain how we get from the two dimensional representation to the 1D version. Or why that works. The entire explanation is two-D then suddenly we are in some optimized form.

Sadly, yet another DP explanation that's more along the lines of memorization compared to actual deep understanding. The existing explanation using the two-D was very intuitive.

This video describe the problem in a great way https://www.youtube.com/watch?v=jaNZ83Q3QGc

nice answer

The corner case for this problem feels strange to me:

Wrong Answer
Your input: 0, []
Output: 0
Expected: 1

Can someone please explain why it expects to have 1 way to change coins
while coins.length = 0 && int amount = 0??

Brute Force Recursive. TLE error

public class CoinChangeRecursiveApproach {
    public int change(int amount, int[] coins) {
        return change(amount, coins, 0);
    }

    private int change(int amount, int[] coins, int index) {
        if (amount == 0) {
            return 1;
        } else if (index >= coins.length) {
            return 0;
        }

        int combinations = 0;
        int coin = coins[index];
        int numOfCoins = 0;

        while (numOfCoins * coin <= amount) {
            combinations += change(amount - (numOfCoins * coin), coins, index + 1);
            numOfCoins++;
        }

        return combinations;
    }
}

Memoization Approach, accepted

public class CoinChangeMemoizationApproach {
    public int change(int amount, int[] coins) {
        Map<Pair, Integer> memo = new HashMap<>();
        return change(amount, coins, 0, memo);
    }

    private int change(int amount, int[] coins, int index, Map<Pair, Integer> memo) {
        if (amount == 0) {
            return 1;
        } else if (index >= coins.length) {
            return 0;
        }

        Pair key = new Pair(amount, index);

        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int combinations = 0;
        int coin = coins[index];
        int numOfCoins = 0;

        while (numOfCoins * coin <= amount) {
            combinations += change(amount - (numOfCoins * coin), coins, index + 1, memo);
            numOfCoins++;
        }

        memo.put(key, combinations);
        return combinations;
    }
}

DFS + backtracking can also solve it. But for large amount of inputs, it will fail due to Time Limit Exceeded 😒